11427. Наилучшее время купить акции

Вам дан массив цен, где prices_i содержит цену имеющейся акции в i-ый день.

Вы хотите максимизировать свою прибыль, выбрав один день для покупки одной акции и выбрав другой день в будущем для продажи этой акции.

Найдите максимальную прибыль, которую можно получить от этой сделки.

Вход. Первая строка содержит размер n (n ≤ 10⁵) массива цен. Вторая строка содержит массив цен – n целых чисел, каждое не более 10⁴.

Выход. Выведите максимальную прибыль, которую можно получить с одной сделки. Если прибыль получить невозможно, выведите 0.

Пример входа 1	Пример выхода 1
8 6 3 6 4 2 4 8 3	6
Пример входа 2	Пример выхода 2
4 5 5 3 2	0

РЕШЕНИЕ

жадные алгоритмы

Анализ алгоритма

Будем поддерживать наименьшее значение цены на префиксе входного массива. Пусть на i-ой итерации min_price = min(prices₀, prices₁, …, prices_i).

Тогда если на i-ой итерации продать акцию, то прибыль составит

prices_i – min_price

Среди всех таких разностей ищем наибольшую. То есть ответ равен

Пример

Рассмотрим первый пример.

Чтобы получить наибольшую прибыль, следует купить акцию за 2, а продать за 8. Таким образом прибыль составит 8 – 2 = 6.

Реализация алгоритма

Читаем входные данные.

scanf("%d", &n);

prices.resize(n);

for (i = 0; i < n; i++)

scanf("%d", &prices[i]);

Инициализируем min_price = ∞.

min_price = INT_MAX;

Искомую максимальную прибыль подсчитываем в переменной res.

res = 0;

Перебираем цены акций.

for (i = 0; i < prices.size(); i++)

{

На i-ой итерации min_price = min(prices₀, prices₁, …, prices_i).

min_price = min(min_price, prices[i]);

Вычисляем ответ res =

res = max(res, prices[i] - min_price);

}

Выводим ответ.

printf("%d\n", res);

Python реализация

import sys

Читаем входные данные.

n = int(input())

prices = list(map(int, input().split()))

Инициализируем min_price = ∞.

min_price = sys.maxsize

Искомую максимальную прибыль подсчитываем в переменной res.

res = 0

Перебираем цены акций.

for price in prices:

На i-ой итерации min_price = min(prices₀, prices₁, …, prices_i).

min_price = min(min_price, price)

Вычисляем ответ res =

res = max(res, price - min_price)

Выводим ответ.

print(res)